// BEGIN CUT HERE
/*
PROBLEM STATEMENT
An old witch is making a love potion. She has a lot of recipes and each of them has the following form:

	S=N1S1+?NkSk
where N1, ? Nk are single-digit integers between 1 and 9, inclusive, S1, ? Sk are names of ingredients, k is an 
integer greater than or equal to 1, and S is name of the resulting potion (all names contain only uppercase letters). 
This means that if she mixes N1 units of S1, ..., Nk units of Sk all together, she will obtain 1 unit of S. There may 
be multiple recipes for the same potion.  In that case, the potion can be obtained using any one of them.  The 
ingredients are also potions, and some of them can be bought at the market.
You want to create 1 unit of the potion called LOVE. You are given vector <string> recipes, each element of which is a 
recipe formatted as described above. You are also given a vector <string> marketGoods and a vector <int> cost. Each 
element of marketGoods is the name of a potion you can purchase at the market.  The i-th element of cost is the cost 
of 1 unit of the i-th potion in marketGoods.  Return the cheapest cost of obtaining 1 unit of LOVE.  If this cost is 
greater than 1,000,000,000, return 1,000,000,001 instead.  If the potion cannot be obtained, return -1 instead.

DEFINITION
Class:MakingPotions
Method:getCost
Parameters:vector <string>, vector <int>, vector <string>
Returns:int
Method signature:int getCost(vector <string> marketGoods, vector <int> cost, vector <string> recipes)


CONSTRAINTS
-marketGoods will contain between 1 and 50 elements, inclusive.
-Each element of marketGoods will contain between 1 and 50 characters, inclusive.
-Each element of marketGoods will contain only uppercase letters ('A'-'Z').
-All elements of marketGoods will be distinct.
-cost will contain the same number of elements as marketGoods.
-Each element of cost will be between 1 and 100, inclusive.
-recipes will contain between 0 and 50 elements, inclusive.
-Each element of recipes will contain between 4 and 50 characters, inclusive.
-Each element of recipes will contain only uppercase letters ('A'-'Z'), non-zero digits ('1'-'9') and the characters 
'+' and '='.
-Each element of recipes will be formatted as described in the problem statement.


EXAMPLES

0)
{"LOVE", "WATER", "HONEY"}
{100, 1, 30}
{"LOVE=5WATER+3HONEY"}

Returns: 95

The LOVE potion is sold at the market, but the witch can make it for a lower cost.

1)
{"WATER", "HONEY", "HOP"}
{2, 6, 9}
{"LOVE=2WATER+4HONEY+2BEER", "BEER=1HOP+3WATER+1HOP"}

Returns: 76

To obtain LOVE, one must make two units of BEER at a cost of 24 each, and then mix 2 units of WATER, 4 units of HONEY 
and 2 units of BEER, which will cost a total of 76.

2)
{"ORANGEJUICE", "APPLEJUICE"}
{6, 4}
{"JUICEMIX=1ORANGEJUICE+1APPLEJUICE"}

Returns: -1

The witch doesn't have a LOVE recipe.


3)
{"WATER", "HONEY", "HOP"}
{1,22,17}
{"LOVE=7WATER+3HONEY", "LOVE=2HONEY+2HOP"}

Returns: 73

The witch has two LOVE recipes and prefers the first one.


4)
{"OIL", "WATER"}
{60, 70}
{"FIRSTPOTION=1OIL+1SECONDPOTION", "SECONDPOTION=4WATER+1FIRSTPOTION", "LOVE=1FIRSTPOTION+1SECONDPOTION"}

Returns: -1

5)
{"HONEYBIT"}

{100}

{"LOVE=6HONEYMEGABYTE","HONEYMEGABYTE=2HONEYFIFTYTWELVEKBYTES",
"HONEYFIFTYTWELVEKBYTES=8HONEYSIXTYFOURKBYTES","HONEYSIXTYFOURKBYTES=8HONEYEIGHTKBYTES",
"HONEYEIGHTKBYTES=8HONEYKBYTE","HONEYKBYTE=2EIGHTBYEIGHTWORDS","EIGHTBYEIGHTWORDS=8EIGHTWORDS",
"EIGHTWORDS=8HONEYWORD","HONEYWORD=8HONEYBYTE","HONEYBYTE=8HONEYBIT"}


Returns: 1000000001



6)
{"WATER"}
{1}
{"LOVE=1LOVE"}

Returns: -1

Some recipes can be useless.

7)
{"MILK","WATER","HOP"}

{6,1,14}
{"NECTAR=4HOP+2MILK","LOVE=5MILK+3BEER","LOVE=2WATER+1LOVE","LOVE=2MIX+1NECTAR",
"MIX=1MILK+1WATER+1HOP","BEER=5WATER+2HOP","LOVE=1NECTAR+3WATER+3HOP","NECTAR=3BEER+1MILK+2MILK"}


Returns: 110



*/
// END CUT HERE
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#ifdef _WIN32
#include <hash_map>
#else
#include <ext/hash_map>
#endif
using namespace std;

#ifdef _WIN32
using namespace stdext;
#else
using namespace __gnu_cxx;
#endif

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define Rep(i,n) for(int i=0;i<(n);++i) 
#define For(i,a,b) for(int i=(a);i<=(b);++i) 
#define ForI(TP,i,coll) for(TP (i)=coll.begin();(i)!=coll.end();(i)++)
#define ForD(i,a,b) for(int i=(a);i>=(b);--i)
#define All(a) a.begin(), a.end()

const int  INF =1000000001;

struct val;
	struct val
	{
		int min_cost;
		bool min_computed;
		val(){min_computed=false;min_cost=INF;}
		
		struct dep_element
		{
			string name;
			int cnt;
		};
		typedef vector<dep_element> dep;
		typedef vector<dep> dep_group;
		dep_group deps;

		int get_min_cost();
	};
map<string, val> costs;

int val::get_min_cost()

		{
			if(min_computed)
				return min_cost;
			// go

			if(min_cost==INF && deps.empty())
				throw -1;

			for(dep_group::iterator it=deps.begin();
				it!=deps.end();
				it++)
			{
				int _cost=0;
				for(dep::iterator itd=it->begin();
					itd!=it->end();
					itd++)
				{
					int _cste=costs[itd->name].get_min_cost();
					if(_cste==INF)
					{
						min_computed=true;
						return INF;
					}
					_cost+=itd->cnt*_cste;
				}

				min_cost=min(min_cost, _cost);
			}
			min_computed=true;
			return min_cost;
		}

class MakingPotions {
public:
	int get(const string& s)
	{
		try
		{
		val& v=costs[s];
		return v.get_min_cost();
		}
		catch(int)
		{
			return -1;
		}
	}

    int getCost(vector <string> marketGoods, vector <int> cost, vector <string> recipes) {
		costs.clear();

		for(int i=0;i<marketGoods.size();i++)
		{
			costs[marketGoods[i]].min_cost=cost[i];
		}

		for(int i=0;i<recipes.size();i++)
		{
			char* s=(char*)recipes[i].c_str();
			string sname=strtok(s,"=");

			costs[sname].deps.push_back(val::dep());
			val::dep& depen=costs[sname].deps.back();

			while( (s=strtok(NULL, "+"))!= NULL )
			{
				int i=s[0]-'0';
				string depname=++s;
				val::dep_element ele={depname,i};
				depen.push_back(ele);
			}
		}

		return get("LOVE");

    }

};

// BEGIN CUT HERE
#define ARRSIZE(x) (sizeof(x)/sizeof(x[0]))

template<typename T> void print( T a ) {
    cerr << a;
}
static void print( long long a ) {
    cerr << a << "L";
}
static void print( string a ) {
    cerr << '"' << a << '"';
}
template<typename T> void print( vector<T> a ) {
    cerr << "{";
    for ( int i = 0 ; i != a.size() ; i++ ) {
        if ( i != 0 ) cerr << ", ";
        print( a[i] );
    }
    cerr << "}" << endl;
}
template<typename T> void eq( int n, T have, T need ) {
    if ( have == need ) {
        cerr << "Case " << n << " passed." << endl;
    } else {
        cerr << "Case " << n << " failed: expected ";
        print( need );
        cerr << " received ";
        print( have );
        cerr << "." << endl;
    }
}
template<typename T> void eq( int n, vector<T> have, vector<T> need ) {
    if( have.size() != need.size() ) {
        cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements.";
        print( have );
        print( need );
        return;
    }
    for( int i= 0; i < have.size(); i++ ) {
        if( have[i] != need[i] ) {
            cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << ".";
            print( have );
            print( need );
            return;
        }
    }
    cerr << "Case " << n << " passed." << endl;
}
static void eq( int n, string have, string need ) {
    if ( have == need ) {
        cerr << "Case " << n << " passed." << endl;
    } else {
        cerr << "Case " << n << " failed: expected ";
        print( need );
        cerr << " received ";
        print( have );
        cerr << "." << endl;
    }
}
// END CUT HERE


// BEGIN CUT HERE
void main( int argc, char* argv[] ) {
    {
        string marketGoodsARRAY[] = {"LOVE", "WATER", "HONEY"};
        vector <string> marketGoods( marketGoodsARRAY, marketGoodsARRAY+ARRSIZE(marketGoodsARRAY) );
        int costARRAY[] = {100, 1, 30};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        string recipesARRAY[] = {"LOVE=5WATER+3HONEY"};
        vector <string> recipes( recipesARRAY, recipesARRAY+ARRSIZE(recipesARRAY) );
        MakingPotions theObject;
        eq(0, theObject.getCost(marketGoods, cost, recipes),95);
    }
    {
        string marketGoodsARRAY[] = {"WATER", "HONEY", "HOP"};
        vector <string> marketGoods( marketGoodsARRAY, marketGoodsARRAY+ARRSIZE(marketGoodsARRAY) );
        int costARRAY[] = {2, 6, 9};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        string recipesARRAY[] = {"LOVE=2WATER+4HONEY+2BEER", "BEER=1HOP+3WATER+1HOP"};
        vector <string> recipes( recipesARRAY, recipesARRAY+ARRSIZE(recipesARRAY) );
        MakingPotions theObject;
        eq(1, theObject.getCost(marketGoods, cost, recipes),76);
    }
    {
        string marketGoodsARRAY[] = {"ORANGEJUICE", "APPLEJUICE"};
        vector <string> marketGoods( marketGoodsARRAY, marketGoodsARRAY+ARRSIZE(marketGoodsARRAY) );
        int costARRAY[] = {6, 4};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        string recipesARRAY[] = {"JUICEMIX=1ORANGEJUICE+1APPLEJUICE"};
        vector <string> recipes( recipesARRAY, recipesARRAY+ARRSIZE(recipesARRAY) );
        MakingPotions theObject;
        eq(2, theObject.getCost(marketGoods, cost, recipes),-1);
    }
    {
        string marketGoodsARRAY[] = {"WATER", "HONEY", "HOP"};
        vector <string> marketGoods( marketGoodsARRAY, marketGoodsARRAY+ARRSIZE(marketGoodsARRAY) );
        int costARRAY[] = {1,22,17};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        string recipesARRAY[] = {"LOVE=7WATER+3HONEY", "LOVE=2HONEY+2HOP"};
        vector <string> recipes( recipesARRAY, recipesARRAY+ARRSIZE(recipesARRAY) );
        MakingPotions theObject;
        eq(3, theObject.getCost(marketGoods, cost, recipes),73);
    }
    {
        string marketGoodsARRAY[] = {"OIL", "WATER"};
        vector <string> marketGoods( marketGoodsARRAY, marketGoodsARRAY+ARRSIZE(marketGoodsARRAY) );
        int costARRAY[] = {60, 70};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        string recipesARRAY[] = {"FIRSTPOTION=1OIL+1SECONDPOTION", "SECONDPOTION=4WATER+1FIRSTPOTION", "LOVE=1FIRSTPOTION+1SECONDPOTION"};
        vector <string> recipes( recipesARRAY, recipesARRAY+ARRSIZE(recipesARRAY) );
        MakingPotions theObject;
        eq(4, theObject.getCost(marketGoods, cost, recipes),-1);
    }
    {
        string marketGoodsARRAY[] = {"HONEYBIT"}
           ;
        vector <string> marketGoods( marketGoodsARRAY, marketGoodsARRAY+ARRSIZE(marketGoodsARRAY) );
        int costARRAY[] = {100}
           ;
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        string recipesARRAY[] = {"LOVE=6HONEYMEGABYTE","HONEYMEGABYTE=2HONEYFIFTYTWELVEKBYTES",
           "HONEYFIFTYTWELVEKBYTES=8HONEYSIXTYFOURKBYTES","HONEYSIXTYFOURKBYTES=8HONEYEIGHTKBYTES",
           "HONEYEIGHTKBYTES=8HONEYKBYTE","HONEYKBYTE=2EIGHTBYEIGHTWORDS","EIGHTBYEIGHTWORDS=8EIGHTWORDS",
           "EIGHTWORDS=8HONEYWORD","HONEYWORD=8HONEYBYTE","HONEYBYTE=8HONEYBIT"}
           ;
        vector <string> recipes( recipesARRAY, recipesARRAY+ARRSIZE(recipesARRAY) );
        MakingPotions theObject;
        eq(5, theObject.getCost(marketGoods, cost, recipes),1000000001);
    }
    {
        string marketGoodsARRAY[] = {"WATER"};
        vector <string> marketGoods( marketGoodsARRAY, marketGoodsARRAY+ARRSIZE(marketGoodsARRAY) );
        int costARRAY[] = {1};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        string recipesARRAY[] = {"LOVE=1LOVE"};
        vector <string> recipes( recipesARRAY, recipesARRAY+ARRSIZE(recipesARRAY) );
        MakingPotions theObject;
        eq(6, theObject.getCost(marketGoods, cost, recipes),-1);
    }
    {
        string marketGoodsARRAY[] = {"MILK","WATER","HOP"}
           ;
        vector <string> marketGoods( marketGoodsARRAY, marketGoodsARRAY+ARRSIZE(marketGoodsARRAY) );
        int costARRAY[] = {6,1,14};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        string recipesARRAY[] = {"NECTAR=4HOP+2MILK","LOVE=5MILK+3BEER","LOVE=2WATER+1LOVE","LOVE=2MIX+1NECTAR",
           "MIX=1MILK+1WATER+1HOP","BEER=5WATER+2HOP","LOVE=1NECTAR+3WATER+3HOP","NECTAR=3BEER+1MILK+2MILK"}
           ;
        vector <string> recipes( recipesARRAY, recipesARRAY+ARRSIZE(recipesARRAY) );
        MakingPotions theObject;
        eq(7, theObject.getCost(marketGoods, cost, recipes),110);
    }
}
// END CUT HERE

